package sort;

public class Sort {
    //选择排序 优化
    public void selectSort(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = right;
            for (int i = left; i <= right; i++) {
                if (array[minIndex] > array[i]) {
                    minIndex = i;
                }
                if (array[maxIndex] < array[i]) {
                    maxIndex = i;
                }
            }
            swap(array,left,minIndex);
            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }
    //快速排序
    //时间复杂度 : o(n * logn)
    //      最好情况下 : o(n*logn)
    //      最坏情况下 : o(n^2)  有序.逆序的情况下
    //空间复杂度 :
    //      最好情况下 : o(logn)
    //      最坏情况下 : o(n)
    public void quickSort(int[] array) {
        quick(array,0,array.length - 1);
    }
    public void quick(int[] array, int s, int e) {
        if (s >= e) {
            return;
        }
        //这个优化 主要是减少递归的次数
        if (e - s <= 14) {
            //插入排序
            insertSort(array,s,e);
            return;
        }
        //三数取中法
        int mid = midThree(array,s,e);
        swap(array,s,mid);

        int pivot = partintion2(array,s,e);
        quick(array,s,pivot - 1);
        quick(array,pivot + 1,e);
    }
    //挖坑法
    public int partition(int[] array, int left, int right) {
        int temp = array[left];
        while (left < right) {
            while (left < right && array[right] >= temp) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= temp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = temp;
        return left;
    }
    //Hoare法
    public int partition1(int[] array, int left, int right) {
        int temp = array[left];
        int i = left;
        while(left < right) {
            while (left < right && array[right] >= temp) {
                right--;
            }
            while(left < right && array[left] <= temp) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,i);
        return left;
    }
    //前后指针法
    //注意 prev 指向的值永远都是比关键字小或者大的最后一个值
    public int partintion2(int[] array, int left, int right) {
        int cur = left + 1;
        int prev = left;
        while(cur <= right) {
            if(array[cur] < array[left] && (++prev != cur)) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }
    //返回三个数当中中间大的数字
    public int midThree(int[] array, int left, int right) {
        int mid = left + (right - left) /2;
        if (array[left] < array[right]) {
          if (array[right] < array[mid]) {
              return right;
          } else if (array[mid] < array[left]) {
              return left;
          } else {
              return mid;
          }
        } else {
            if (array[right] > array[mid]) {
                return right;
            } else if (array[mid] > array[left]) {
                return left;
            } else {
                return mid;
            }
        }
    }
    //插入排序
    public void insertSort(int[] array, int s, int e) {
        for (int i = s; i <= e; i++) {
            int temp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] > temp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = temp;
        }
    }
    //交换
    public void swap(int[] array, int x, int y) {
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }
}
